Who are the influential people in an online social network? The answer tothis question depends not only on the structure of the network, but also ondetails of the dynamic processes occurring on it. We classify these processesas conservative and non-conservative. A random walk on a network is an exampleof a conservative dynamic process, while information spread isnon-conservative. The influence models used to rank network nodes can besimilarly classified, depending on the dynamic process they implicitly emulate.We claim that in order to correctly rank network nodes, the influence model hasto match the details of the dynamic process. We study a real-world network onthe social news aggregator Digg, which allows users to post and vote for newsstories. We empirically define influence as the number of in-network votes auser's post generates. This influence measure, and the resulting ranking,arises entirely from the dynamics of voting on Digg, which representsnon-conservative information flow. We then compare predictions of different influence models with this empiricalestimate of influence. The results show that non-conservative models are betterable to predict influential users on Digg. We find that normalizedalpha-centrality metric turns out to be one of the best predictors ofinfluence. We also present a simple algorithm for computing this metric and theassociated mathematical formulation and analytical proofs.
展开▼
